package sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 描述:
 *
 * @author
 * @created 2022/1/5 20:05
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 6, 67, 7, 87, 4, 3, 23, 45, 6, 7, 78, 6, 4, 43, 5, 6, 67, 67};
        ArrayList<Integer> integers = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            integers.add(arr[i]);
        }
        List<Integer> integers1 = bucketSort(integers, 10);
        System.out.println(Arrays.toString(integers1.toArray()));
    }

    public static List<Integer> bucketSort(List<Integer> arr, int bucketCap) {
        if (arr == null || arr.size() < 2) {
            return arr;
        }
        /*获取最大和最小*/
        int max = arr.get(0);
        int min = arr.get(0);
        for (int i = 0; i < arr.size(); i++) {
            if (max < arr.get(i)) {
                max = arr.get(i);
            }
            if (min > arr.get(i)) {
                min = arr.get(i);
            }
        }
        /*获取桶的数量*/
        int bucketCount = (max - min) / bucketCap + 1;
        /*初始化桶*/
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
        /*将原始数组中的数据分配到桶中*/
        for (int i = 0; i < arr.size(); i++) {
            bucketArr.get((arr.get(i) - min) / bucketCap).add(arr.get(i));
        }
        /*查看桶中的数据分布*/
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            if (bucketCap == 1) {
                for (int j = 0; j < bucketArr.get(i).size(); j++) {
                    result.add(bucketArr.get(i).get(j));
                }
            } else {
                if (bucketCount == 1) {
                    bucketCap--;
                }
                System.out.println("对第" + i + "桶中的数据继续使用桶排序");
                List<Integer> temp = bucketSort(bucketArr.get(i), bucketCap);
                for (int j = 0; j < temp.size(); j++) {
                    result.add(temp.get(j));
                }
            }
        }
        return result;
    }

}
